
/**
 * 
 * 矩形绘制
 * 
 * 题目描述

实现一个简单的绘图模块，绘图模块仅支持矩形的绘制和擦除

当新绘制的矩形与之前的图形重叠时，对图形取并集
当新擦除的矩形与之前的图形重叠时，对图形取差集
给定一系列矩形的绘制和擦除操作，计算最终图形的面积。

下面给出示例1和示例2的图示

示例1：



两步绘制的矩形如左侧所示，取并集后得到的图形如右侧所示
示例2：



第一步绘制的矩形在左侧用实线表示，第二步擦除的矩形在左侧用虚线表示，取差集后得到图像如右侧所示
输入描述
绘图模块采用二维坐标系，输入第一行位操作的数量 N，接下来的 N 行格式为：

d x1 y1 x2 y2，d表示进行绘制操作，(x1, y1)为矩形左上角坐标，(x2, y2)为矩形右下角坐标
e x1 y1 x2 y2，e表示进行擦除操作，(x1, y1)为矩形左上角坐标，(x2, y2)为矩形右下角坐标
坐标为整数，且数据范围为 [-100, 100]，用例保证坐标有效

输出描述
输出最终图形的面积

用例
输入	2
d 0 2 2 0
d -1 1 1 -1
输出	7
说明	无
输入	2
d 0 2 2 0
e -1 1 1 -1
输出	3
说明	无


 */

import java.util.ArrayList;
import java.util.Scanner;

/**
  * 
  题目解析
本题是 LeetCode - 850 矩形面积 II- 程序员阿甘的CSDN博客 的变形题，要想做出本题，需要将前面这题先做出来，大家可以先看下leetcode这题。

本题相较于 leetcode 这题的变化在于，多了擦除矩形的动作。

基于 leetcode 850 的思路，扫描线扫描范围 [preX, curX]，我们需要求出处于该水平区间的所有矩形，将对应矩形的垂直方向区间求解出来，基于区间问题，求解所有垂直方向区间的并集长度。

本题的矩形分为两种：绘制矩形 和 擦除矩形

处于扫描线范围 [preX, curX] 中的矩形，既可能是绘制矩形，也可以是擦除矩形。

此时如果 绘制矩形垂直方向区间 和 擦除矩形垂直方向区间 有交集，则交集部分需要去除，剩余的差集部分区间才是有效的，我们假设差集部分长度之和为 height，那么扫描线扫描的面积为 (curX - preX) * height。

2024.09.29
需要注意的是，本题的绘制和擦除是有顺序性的，
比如：
2
d 0 2 2 0
e -1 1 1 -1
的结果是3。
 
比如：
2
e -1 1 1 -1
d 0 2 2 0
的结果应该是4。因为擦除的时候，对应区域没有绘制的矩形，而擦除之后，对应擦除区域又被绘制了。
那么如何求解两个区间的差集呢？

其实可以转化为求解两个区间的交集，然后将目的区间去除交集区间，即为差集区间。

主要有如下情况：



s1 >= e，因此：[s, e] - [s1, e1] 的差集为：[s, e]


s <= s1 < e <= e1，因此：[s, e] - [s1, e1] 的差集为：[s, s1]


s1 < s < e < e1，因此：[s, e] - [s1, e1] 的差集为：[]
 

s < s1 < e1 < e，因此：[s, e] - [s1, e1] 的差集为：[s, s1] 和 [e1, e]


s1 <= s < e1  <= e，因此：[s, e] - [s1, e1] 的差集为：[e1, e]


e1 <= s，因此：[s, e] - [s1, e1] 的差集为：[s, e]

  */
public class 矩形绘制 {
    
    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
 
        int n = sc.nextInt();
 
        int[][] rects = new int[n][5];
        for (int i = 0; i < n; i++) {
            rects[i][0] = sc.next().charAt(0); // op
            rects[i][1] = sc.nextInt(); // x1
            rects[i][2] = sc.nextInt(); // y1
            rects[i][3] = sc.nextInt(); // x2
            rects[i][4] = sc.nextInt(); // y2
        }
 
        System.out.println(solution(rects));
    }
 
    public static int solution(int[][] rects) {
        // 统计所有矩形的左边边、右边边所在位置的x坐标
        ArrayList<Integer> listX = new ArrayList<>();
 
        for (int[] rect : rects) {
            listX.add(rect[1]); // 矩形左边边x坐标位置
            listX.add(rect[3]); // 矩形右边边x坐标位置
        }
 
        // 所有x坐标升序（每个x视为一条扫描线）
        listX.sort((a, b) -> a - b);
 
        // 记录所有矩形并集面积
        int ans = 0;
 
        for (int i = 1; i < listX.size(); i++) {
            // 前一个扫描线x坐标
            int preX = listX.get(i - 1);
            // 当前扫描线x坐标
            int curX = listX.get(i);
 
            // 相邻两个扫描线的距离
            int width = curX - preX;
 
            // 距离为0, 则跳过
            if (width == 0) continue;
 
            // 处于水平方向 [preX, curX] 范围，对应的垂直方向上 绘制矩形 的区间
            ArrayList<int[]> draw_lines = new ArrayList<>();
 
            for (int[] rect : rects) {
                int op = rect[0], x1 = rect[1], y1 = rect[2], x2 = rect[3], y2 = rect[4];
 
                if (x1 <= preX && curX <= x2) {
                    int[] line = new int[]{y2, y1};
 
                    if (op == 'd') {
                        draw_lines.add(line);
                    } else {
                        draw_lines = getDiff(draw_lines, line);
                    }
 
                }
            }
 
            ans += width * getUnionLen(draw_lines);
        }
 
        return ans;
    }
 
    // 区间差集: draw_line - erase_line
    public static ArrayList<int[]> getDiff(ArrayList<int[]> draw_lines, int[] erase_line) {
        ArrayList<int[]> lines = new ArrayList<>();
 
        int s1 = erase_line[0];
        int e1 = erase_line[1];
 
        for (int[] drawLine : draw_lines) {
            int s = drawLine[0];
            int e = drawLine[1];
 
            if (s1 >= e || s >= e1) {
                lines.add(new int[]{s, e});
            } else if (s < s1 && e1 < e) {
                lines.add(new int[]{s, s1});
                lines.add(new int[]{e1, e});
            } else if (s <= s1 && e <= e1) {
                lines.add(new int[]{s, s1});
            } else if (s1 <= s && e1 <= e) {
                lines.add(new int[]{e1, e});
            }
        }
 
        return lines;
    }
 
    // 区间并集长度
    public static int getUnionLen(ArrayList<int[]> lines) {
        // 将处于水方向区间 [x1, x2] 的所有垂直方向区间排序：按照起始位置升序, 如果起始位置相同, 则按照结束位置降序，这样排序的目的是保证排序后，前面的区间尽可能可以覆盖后面的区间
        lines.sort((lineA, lineB) -> lineA[0] != lineB[0] ? lineA[0] - lineB[0] : lineB[1] - lineA[1]);
 
        // 记录lines多个区间，求长度之和，（重叠部分只计算一次）
        int len = 0;
 
        int last_end = Integer.MIN_VALUE;
        for (int[] line : lines) {
            int start = line[0];
            int end = line[1];
 
            // 如果 last_end >= end, 则当前区间被上一个区间完全覆盖，因此可以跳过
            if (last_end < end) {
                // 则当前区间的不重叠部分是 [max(start, last_end), end]
                len += end - Math.max(start, last_end);
                // 更新last_end
                last_end = end;
            }
        }
 
        return len;
    }

}
